// 2025/3/31
// https://leetcode.cn/problems/coin-change/description/?envType=study-plan-v2&envId=top-100-liked
// 零钱兑换

class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            sort(coins.begin(), coins.end());
            vector<int> dp(amount + 1, 0);
            int n = coins.size();
            for(int i = 1; i <= amount; i++)
            {
                int minn = amount + 1;
                for(int j = 0; j < n && coins[j] <= i; j++)
                {
                    minn = min(minn, dp[i - coins[j]]);
                }
                dp[i] = minn + 1;
            }
            return dp[amount] > amount ? -1 : dp[amount];
        }
    };

